public class MaxProfit2 {
    // 买卖股票的最佳时机2
    // https://www.nowcoder.com/practice/9e5e3c2603064829b0a0bbfca10594e9?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public int maxProfit (int[] prices) {
        // write code here
        int len = prices.length;
        // f[i]表示第i天处于买入状态时的最大利益
        int[] f = new int[len];
        // g[i]表示第i天处于卖出状态时候的最大利益
        int[] g = new int[len];
        // 状态转移方程，因为可以多次买入卖出，所以是可以从卖出状态转换为买入状态的
        // f[i] = max(f[i-1], g[i-1] - prices[i])
        // g[i] = max(g[i-1], f[i-1]  + prices[i])
        f[0] = -prices[0];
        for (int i = 1; i < len; i++) {
            f[i] = Math.max(f[i-1], g[i-1] - prices[i]);
            g[i] = Math.max(g[i-1], f[i-1] + prices[i]);
        }
        return g[len-1];
    }
}
